//自己用链表为底层实现队列
//注意:可以在类中再增加一个size字段,用于更方便的来判断队列是否为空
public class MyQueue {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val){
            this.val = val;
        }
    }

    //链表的头结点
    public ListNode head;

    //链表的尾结点
    public ListNode last;

    //入队列(链表中的尾插)
    public void offer(int val){
        ListNode node = new  ListNode(val);
        if(head == null){
            head = last = node;
        }else{
            last.next = node;
            node.prev = last;
            last = last.next;
        }
    }

    //出队列(链表中的头删)
    public int poll(){
        if(head == null) {
            return -1;
        }
        int ret = head.val;
        if(head.next == null){
            head = null;
            last = null;
        }else{
            head = head.next;
            head.prev = null;
        }
        return ret;
    }

    //查看队头元素但是不出队列
    public int peek(){
        if(head == null){
            return - 1;
        }
        return head.val;
    }

    //判断队列是否为空
    public boolean empty(){
        return head == null;
    }
}
